#pragma once

#include <string>
#include <vector>

namespace solution_097
{

class Solution
{
public:
    bool isInterleave(std::string s1, std::string s2, std::string s3)
    {
        if (s1.empty())
            return s2 == s3;
        if (s2.empty())
            return s1 == s3;
        if (s1.size() + s2.size() != s3.size())
            return false;

        std::vector lookup(s1.size() + 1, std::vector(s2.size() + 1, '\0'));
        lookup[0][0] = 1;
        for (size_t i = 0; i <= s1.size(); ++i) {
            for (size_t j = 0; j <= s2.size(); ++j) {
                if (i + j == 0)
                    continue;
                auto ch3 = s3.at(i + j - 1);
                if (i == 0) {
                    lookup[i][j] = (j > 0 && lookup[i][j-1] && s2.at(j - 1) == ch3);
                } else if (j == 0) {
                    lookup[i][j] = (i > 0 && lookup[i-1][j] && s1.at(i - 1) == ch3);
                } else {
                    lookup[i][j] = (lookup[i][j-1] && s2.at(j - 1) == ch3) ||
                                   (lookup[i-1][j] && s1.at(i - 1) == ch3);
                }
            }
        }
        return lookup.back().back();
    }
};

}  /* namespace solution_097 */
